package io.github.maojian.bianrysearch;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Auther: jian.mao
 * @Date: 2022/5/20 09:32
 * @Description:
 */
public class Q436 {

    public int[] findRightInterval(int[][] intervals) {
        int length = intervals.length;
        int[][] startIntervals = new int[length][2];
        for (int i = 0; i < length; i++) {
            startIntervals[i][0] = intervals[i][0];
            startIntervals[i][1] = i;
        }
        Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            int left = 0;
            int right = length - 1;
            int target = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                // endi <= startj
                if (intervals[i][1]  <= startIntervals[mid][0]) {
                    target = startIntervals[mid][1];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            result[i] = target;
        }
        return result;
    }


    @Test
    public void test() {
        int[][] intervals = new int[][]{{1, 4}, {2, 3}, {3, 4}};
        Arrays.stream(findRightInterval(intervals)).forEach(System.out::println);
    }
}
